package first

import "gitee.com/themoonstone/toOffer/first/original"

/*
	给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动k个位置。

	示例 1：
	输入：head = [1,2,3,4,5], k = 2
	输出：[4,5,1,2,3]
	示例 2：
	输入：head = [0,1,2], k = 4
	输出：[2,0,1]

	提示：
	链表中节点的数目在范围 [0, 500] 内
	-100 <= Node.val <= 100
	0 <= k <= 2 * 109

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/rotate-list
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func rotateRight(head *original.ListNode, k int) *original.ListNode {
	// 1. 求长度
	if nil == head {
		return nil
	}
	cur := head
	size := getSize(cur)
	k = k % size
	// 2. 链表成环
	oldHead := head
	for head.Next != nil {
		head = head.Next
	}
	head.Next = oldHead
	// 3. 移动指针
	for i := 1; i < size-k; i++ {
		oldHead = oldHead.Next
	}
	newHead := oldHead.Next
	oldHead.Next = nil
	return newHead
}

func getSize(cur *original.ListNode) int {
	size := 0
	for cur != nil {
		size++
		cur = cur.Next
	}
	return size
}
